链表问题学习大总结

发表于 | 分类于 | 阅读次数
字数统计 2,551 | 阅读时长 10

链表问题学习大总结

linkedlist 链表问题各种被虐，基础非常不牢靠，所以要多花时间补基础，索性搜索一下链表问题做一个大总结。

0. 链表的定义

1
2
3
4
5
6
7
private static class Node(){
	int value;
	Node next;
	public Node(int value){            
		this.value=value;
	}
}

1. 求链表的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//判断链表是否为空，如果空则没法赋值,同时不应该改动原来链表的头指针的指向,
//复杂度为O(n)
private int getListLength(Node head){
	if (head == null)
			return 0;
	
	int len=0;
	Node cur = head;
	while(cur!==null){
		len++;
		cur=cur.next;
	}
	return len;
}

2. 求单链表翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//  翻转链表（遍历）  
   // 从头到尾遍历原链表，每遍历一个结点，  
   // 将其摘下放在新链表的最前端。  
   // 注意链表为空和只有一个结点的情况。时间复杂度为O（n）
private Node reverse (Node head){
	Node cur=head;
	Node rehead=null;
	if (head == null || head.next==null) {
		return head;
	}
	while(cur!=null){//较难理解
		Node temp = cur;
		cur=cur.next;
		temp.next = rehead;
		rehead=	temp;		
	}
	return rehead;
}
//翻转链表（递归）
private Node reverse(Node head){
	Node rehead=null;
	if (head==null||head.next==null) {
		return head;			
	}
	Node rehead=reverse(head.next)
	head.next.next=head;
	head.next=null;
	return rehead;
}

3. 求倒数第K个点

题目描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。 分析：设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。very tricky 代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private Node findBottomKth(Node head,int k){
	Node slow = null;
	Node fast = null;
	slow=head;
	fast=head;
	int i=k;
	for (;i>0&&fast!=null;i--) {
		fast=fast.next;
	}
	while(fast!=null){
		fast=fast.next;
		slow=slow.next;
	}
	return slow;
}

4. 查找链表中间的值

这题的方法思路和上一题一样，采用快慢两个指针，步长分别为1和2，遍历链表，直到快指针为null停止。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private Node getListMid(Node head){
	if (head==null) {
		return 0;			
	}
	Node slow,fast;
	slow=head;
	fast=head;
	while(fast!=null&&fast.next!=null){
		fast=fast.next();
		if (fast.next!=null) {
			fast=fast.next				
		}
		else return slow;
		slow=slow.next;
	}
}

5. 从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/** 
    * 从尾到头打印单链表 
    * 对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。所以，这一题要么自己使用栈，要么让系统使用栈，也就是递归。注意链表为空的情况 
    * 。时间复杂度为O（n） 
    */  
public void printReverseLink(Node head){
	Stack<Node> st =new Stack<Node>();
	if (head==null) return;
	Node cur = head;
	while (cur!=null) {
		st.push(cur);
		cur=cur.next;
	}
	while (!s.empty()) {
		System.out.print(st.pop().vaule+" ");
	}
}
/** 
    * 使用递归 
    */
public void printReverseLink(Node head){
	if (head==null) return;
	else{
		Node cur = head;
		printReverseLink(cur.next);
		System.out.print(cur.vaule+" ");		
	}
}

6. 判断链表是否有环，并找到环的入口

题目描述：输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？ 解题思路： 由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。 为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有： p1走的路径： a+b ＝ n； p2走的路径： a+b+k*L = 2*n； p2 比 p1 多走了k圈环路，总路程是p1的2倍 根据上述公式可以得到 k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。 显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。 代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public Node findLoopPort(head){
	Node slow;
	Node fast;
	slow=head;
	fast=head;
	while(fast!=null&&fast.next!=null){
		slow=slow.next;
		fast=fast.next.next;
		if (slow==fast) break;
	}
	if (slow!=fast) {
		return null;
	}
	else{
		fast=head;
		while(fast!=slow) {
			fast=fast.next;
			slow=slow.next;
		}
		return slow;
	}
}

7.判断链表是否相交

**题目描述：**给出两个单向链表的头指针（如下图所示），

比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。 解题思路： 直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。 针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个节点是否在hash表出现，如果所有的第二个链表的节点都能在hash表中找到，即说明第二个链表与第一个链表有相同的节点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？ 转换为环的问题。把第二个链表接在第一个链表后面，如果得到的链表有环，则说明两个链表相交。如何判断有环的问题上面已经讨论过了，但这里有更简单的方法。因为如果有环，则第二个链表的表头一定也在环上，即第二个链表会构成一个循环链表，我们只需要遍历第二个链表，看是否会回到起始点就可以判断出来。这个方法的时间复杂度是线性的，空间是常熟。 进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。 所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)，显然比解法三更胜一筹。 

1
2
3
4
5
6
7
8
9
10
public boolean isConnected(Node head1, Node head2){
	Node tail1 = head1;
	Node tail2 =head2;
	while(tail1!=null)
		tail1=tail1.next;
		while(tail2!=null)
			tail2=tail2.next;
		return tail2==tail1;
}

8.求两个单链表相交的第一个节点

题目描述：如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？ 分析：采用对齐的思想。计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动L2 - L1个节点，然后再同时向后移动p1 , p2，直到 p1 = p2。相遇的点就是相交的第一个节点。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public Node getFirstCommonNode(Node head1, Node head2){
	Node tail1 = head1;
	Node tail2 =head2;
	int l1=0;
	while(tail1!=null)//list1 长度l1
		{	
			tail1=tail1.next;
			l1++;
		}
	int l2=0;
		while(tail2!=null)//list2 长度l2
		{
			tail2=tail2.next;
			l2++;
		}
		if (tail1!=tail2) {	//如果不相等直接返回空，结束
			return null;
		}
		tail1=head1;//再回到头，长的链表先走|l1-l2|，再同步走直到相交
		tail2=head2;
		if (l1>l2) {
			int k=l1-k2;
			for(;k!=0;k--)
				tail1=tail1.next;
		}
		else{
			int k=l2-l1;
			for (;k!=0;k--) {
				tail2=tail2.next;
			}
		}
		while(tail1!=tail2){
			tail1=tail1.next;
			tail2=tail2.next;
		}
		return tail1;
}

9. 在O(1)时间删除链表节点

**题目描述：**给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题] 分析：本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
	 /** 
     * 给出一单链表头指针head和一节点指针toBeDeleted，O(1)时间复杂度删除节点tBeDeleted 
     * 对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点 
     * ，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表， 
     * 链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点 
     * ，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1) 
     */  
    public void delete(Node head, Node toDelete){  
        if(toDelete == null){  
            return;  
        }  
        if(toDelete.next != null){          // 要删除的是一个中间节点  
            toDelete.val = toDelete.next.val;       // 将下一个节点的数据复制到本节点!  
            toDelete.next = toDelete.next.next;  
        }  
        else{       // 要删除的是最后一个节点！  
            if(head == toDelete){       // 链表中只有一个节点的情况    
                head = null;  
            }else{  
                Node node = head;  
                while(node.next != toDelete){   // 找到倒数第二个节点  
                    node = node.next;  
                }  
                node.next = null;  
            }  
        }  
    }       
}

10. 参考：

面试精选：链表问题集锦 面试大总结之一：Java搞定面试中的链表题目

请我喝杯咖啡吧！